home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / search.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  8KB  |  298 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)search.c    5.2 (Berkeley) 4/8/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include "btree.h"
  44. #include "utils.h"
  45.  
  46. /*
  47.  *  _BT_FIRST -- Find the first item in the tree that matches the supplied
  48.  *         key.
  49.  *
  50.  *    This routine supports deletion.  When the user supplies a key to
  51.  *    be deleted, we find the first one, and iteratively delete all the
  52.  *    matching ones that follow it.
  53.  *
  54.  *    Parameters:
  55.  *        t -- btree in which to find first occurrence
  56.  *        key -- key to find
  57.  *
  58.  *    Returns:
  59.  *        The BTITEM for the matching item.  If there's no match,
  60.  *        this may point to the first item > than the supplied key,
  61.  *        or off the end of the page.
  62.  *
  63.  *    Warnings:
  64.  *        The BTITEM returned is in static space and will be overwritten
  65.  *        by the next search of any kind in any btree.
  66.  */
  67.  
  68. BTITEM *
  69. _bt_first(t, key)
  70.     BTREE_P t;
  71.     DBT *key;
  72. {
  73.     BTHEADER *h;
  74.     BTITEM *item;
  75.     index_t next;
  76.     int r;
  77.  
  78.     /* find any matching item */
  79.     item = _bt_search(t, key);
  80.     h = t->bt_curpage;
  81.     next = NEXTINDEX(h);
  82.  
  83.     /* if we're off the end of the page, search failed and we're done */
  84.     if (item->bti_index >= next)
  85.         return (item);
  86.  
  87.     /* as long as we have an exact match, walk backwards */
  88.     while ((r = _bt_cmp(t, key->data, item->bti_index)) == 0) {
  89.  
  90.         /* at start of page? */
  91.         if (item->bti_index == 0) {
  92.  
  93.             /* if no prev page, we're done */
  94.             if (h->h_prevpg == P_NONE)
  95.                 return (item);
  96.  
  97.             /* walk backward, skipping empty pages */
  98.             do {
  99.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  100.                     return ((BTITEM *) NULL);
  101.                 h = t->bt_curpage;
  102.             } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
  103.  
  104.             if (NEXTINDEX(h) != 0)
  105.                 item->bti_index = NEXTINDEX(h) - 1;
  106.             else
  107.                 item->bti_index = 0;
  108.  
  109.             item->bti_pgno = h->h_pgno;
  110.         } else {
  111.             item->bti_index--;
  112.         }
  113.     }
  114.  
  115.     /* if we went too far backwards, step forward one entry */
  116.     if (r > 0) {
  117.         if (++(item->bti_index) >= NEXTINDEX(h)
  118.             && h->h_nextpg != P_NONE) {
  119.  
  120.             /* walk forward, skipping empty pages */
  121.             do {
  122.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  123.                     return ((BTITEM *) NULL);
  124.                 h = t->bt_curpage;
  125.             } while (h->h_nextpg != P_NONE && NEXTINDEX(h) == 0);
  126.  
  127.             item->bti_index = 0;
  128.             item->bti_pgno = h->h_pgno;
  129.         }
  130.     }
  131.  
  132.     /* got it */
  133.     return (item);
  134. }
  135.  
  136. /*
  137.  *  _BT_SEARCH, _BT_SEARCHR -- Search for a particular key in the tree.
  138.  *
  139.  *    Parameters:
  140.  *        t -- btree in which to search
  141.  *        key -- key to find
  142.  *
  143.  *    Returns:
  144.  *        BTITEM for matching item, if any, or the BTITEM for the
  145.  *        location of the key, if it were in the tree.
  146.  *
  147.  *    Warnings:
  148.  *        The BTITEM returned is in static memory, and will be
  149.  *        overwritten by the next search of any kind in any tree.
  150.  */
  151.  
  152. BTITEM *
  153. _bt_search(t, key)
  154.     BTREE_P t;
  155.     DBT *key;
  156. {
  157.     /* we want to start all of our searches at the root */
  158.     if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
  159.         return ((BTITEM *) NULL);
  160.  
  161.     return (_bt_searchr(t, key));
  162. }
  163.  
  164. BTITEM *
  165. _bt_searchr(t, key)
  166.     BTREE_P t;
  167.     DBT *key;
  168. {
  169.     BTHEADER *h = t->bt_curpage;
  170.     index_t index;
  171.     IDATUM *id;
  172.     DATUM *d;
  173.     static BTITEM item;
  174.  
  175.     /* do a binary search on the current page */
  176.     index = _bt_binsrch(t, key->data);
  177.  
  178.     /*
  179.      *  At this point, the binary search terminated because the endpoints
  180.      *  got too close together, or we have a match.  Figure out which
  181.      *  case applies and decide what to do based on the page type.
  182.      */
  183.     if (h->h_flags & F_LEAF) {
  184.         item.bti_pgno = h->h_pgno;
  185.         item.bti_index = index;
  186.         if (index < NEXTINDEX(h))
  187.             d = (DATUM *) GETDATUM(h,index);
  188.         else
  189.             d = (DATUM *) NULL;
  190.  
  191.         item.bti_datum = d;
  192.         return(&item);
  193.     } else {
  194.         id = (IDATUM *) GETDATUM(h, index);
  195.         if (_bt_push(t, h->h_pgno) == RET_ERROR)
  196.             return ((BTITEM *) NULL);
  197.         if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  198.             return ((BTITEM *) NULL);
  199.         return (_bt_searchr(t, key));
  200.     }
  201. }
  202.  
  203. /*
  204.  *  _BT_BINSRCH -- Do a binary search for a given key on the current page.
  205.  *
  206.  *    Searches on internal pages are handled slightly differently from
  207.  *    searches on leaf pages.  This is because internal page searches
  208.  *    find the largest item <= key in the tree, and leaf searches find
  209.  *    the smallest item >= key.  This guarantees that leaf page searches
  210.  *    leave us pointing at the item's correct position, and internal
  211.  *    searches descend the tree correctly.
  212.  *
  213.  *    Parameters:
  214.  *        t -- tree to search
  215.  *        key -- key we're looking for
  216.  *
  217.  *    Returns:
  218.  *        Index of the line pointer array entry for the (closest)
  219.  *        match to key on the current page, with "closest" as defined
  220.  *        above.
  221.  */
  222.  
  223. index_t
  224. _bt_binsrch(t, key)
  225.     BTREE_P t;
  226.     char *key;
  227. {
  228.     index_t lbound, ubound, cur = 0;
  229.     BTHEADER *h = t->bt_curpage;
  230.     int match = 0;
  231.     int r;
  232.  
  233.     lbound = 0;
  234.     ubound = NEXTINDEX(h);
  235.     if (ubound > 0)
  236.         --ubound;
  237.  
  238.     /* do a binary search on the current page */
  239.     while ((ubound - lbound) > 1) {
  240.         cur = lbound + ((ubound - lbound) / 2);
  241.         r = _bt_cmp(t, key, cur);
  242.  
  243.         if (r > 0)
  244.             lbound = cur + 1;
  245.         else if (r < 0)
  246.             ubound = cur;
  247.         else {
  248.             match++;
  249.             break;
  250.         }
  251.     }
  252.  
  253.     /*
  254.      *  At this point, the binary search terminated because the endpoints
  255.      *  got too close together, or we have a match.  Figure out which
  256.      *  case applies, decide what to do based on the page type (leaf or
  257.      *  internal), and do the right thing.
  258.      */
  259.     if (match) {
  260.         return (cur);
  261.     } else if (ubound != lbound) {
  262.         if (h->h_flags & F_LEAF) {
  263.             r = _bt_cmp(t, key, lbound);
  264.             if (r <= 0) {
  265.                 return (lbound);
  266.             }
  267.         } else {
  268.             r = _bt_cmp(t, key, ubound);
  269.  
  270.             /* for internal nodes, move as far left as possible */
  271.             if (r < 0) {
  272.                 r = _bt_cmp(t, key, lbound);
  273.                 if (r < 0 && lbound > 0)
  274.                     --lbound;
  275.                 return (lbound);
  276.             } else {
  277.                 return (ubound);
  278.             }
  279.         }
  280.     }
  281.  
  282.     if (h->h_flags & F_LEAF) {
  283.         if (ubound < NEXTINDEX(h)) {
  284.             r = _bt_cmp(t, key, ubound);
  285.             if (r > 0)
  286.                 ubound++;
  287.         }
  288.     } else {
  289.         /* for internal pages, move as far left as possible */
  290.         if (ubound == NEXTINDEX(h))
  291.             ubound--;
  292.  
  293.         while (_bt_cmp(t, key, ubound) < 0)
  294.             ubound--;
  295.     }
  296.     return (ubound);
  297. }
  298.